package danran.bfs;

import java.util.*;

/**
 * @Classname InvalidParentheses
 * @Description TODO
 * @Date 2021/8/28 13:59
 * @Created by ASUS
 */
public class InvalidParentheses {

    public static void main(String[] args) {
        System.out.println(new InvalidParentheses().removeInvalidParentheses(")("));
    }

    public List<String> removeInvalidParentheses(String s) {
        if (s == null || s.length() == 0) return new ArrayList<>();
        List<String> ans = new ArrayList<>();
        Queue<String> q = new ArrayDeque<>();
        Set<String> set = new HashSet<>();
        q.offer(s);
        set.add(s);
        boolean find = false;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                String cur = q.poll();
                if (isValid(cur)) {
                    find = true;
                    ans.add(cur);
                }
                if (find) continue;
                assert cur != null;
                List<String> subs = generate(cur);
                for (String sub : subs) {
                    if (!set.contains(sub)) {
                        q.offer(sub);
                        set.add(sub);
                    }
                }
            }
        }
        return ans;
    }

    public boolean isValid(String str) {
        if (str == null) return false;
        if ("".equals(str)) return true;
        Stack<Character> stack = new Stack<>();
        for (char c : str.toCharArray()) {
            if (c == '(') stack.push(c);
            else if (c == ')') {
                if (!stack.isEmpty()) stack.pop();
                else return false;
            }
        }
        return stack.isEmpty();
    }

    public List<String> generate(String str) {
        if (str.length() <= 1) return new ArrayList<>();
        List<String> ans = new ArrayList<>();
        StringBuilder b;
        for (int i = 0; i < str.length(); i++) {
            b = new StringBuilder(str);
            if (str.charAt(i) != '(' && str.charAt(i) != ')') continue;
            ans.add(b.deleteCharAt(i).toString());
        }
        return ans;
    }
}
